from typing import *
from math import inf


class Solution:

    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        l, r = 0, price[-1]
        while l + 1 < r:
            m = ((r - l) >> 1) + l
            last, cnt = -inf, 0
            for v in price:
                if v - last >= m:
                    cnt += 1
                    last = v
            if cnt >= k:
                l = m
            else:
                r = m
        return l


# print(int(1e9))
so = Solution()
print(so.maximumTastiness(price=[13, 5, 1, 8, 21, 2], k=3))
print(so.maximumTastiness([34, 116, 83, 15, 150, 56, 69, 42, 26], 6))


class Solution:

    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        l, r = 0, price[-1]
        while l < r:
            m = ((r - l + 1) >> 1) + l
            last, cnt = -inf, 0
            for v in price:
                if v - last >= m:
                    cnt += 1
                    last = v
            if cnt >= k:
                l = m
            else:
                r = m - 1
        return l


# print(int(1e9))
so = Solution()
print(so.maximumTastiness(price=[13, 5, 1, 8, 21, 2], k=3))
print(so.maximumTastiness([34, 116, 83, 15, 150, 56, 69, 42, 26], 6))